﻿using System.Collections.Generic;

namespace Engine.Collections
{
    public class SortedList<T> : System.Collections.CollectionBase
    {
        private readonly IComparer<T> m_Comparator;

        public SortedList(IComparer<T> comparer)
        {
            m_Comparator = comparer;
        }
        public T this[int index]
        {
            get
            {
                return (T) List[index];
            }
        }
        public int IndexOf(T state)
        {
            int start = 0;
            int end = List.Count - 1;

            while (start <= end)
            {
                int middle = (start + end)/2;
                int comparisonResult = m_Comparator.Compare((T)List[middle], state);

                if (comparisonResult == 0) return middle;
                if (comparisonResult > 0)
                {
                    start = middle + 1;
                    end = List.Count;
                }
                else
                {
                    start = 0;
                    end = middle;
                }
            }
            return -1;
        }
        public void AddRange(System.Collections.ICollection collection)
        {
            foreach (T obj in collection)
                Add(obj);
        }
        public void Add(T state)
        {
            int start = 0;
            int end = List.Count - 1;

            while (start <= end)
            {
                int middle = (start+end)/2;
                int comparisonResult = m_Comparator.Compare(state, (T) List[middle]);

                if (comparisonResult == 0)
                {
                    while ((middle) >= 0 && m_Comparator.Compare(state, (T) List[middle]) == 0)
                    {
                        middle = middle - 1;
                    }

                    if (middle < 0)
                        List.Insert(0, state);
                    else
                        List.Insert(middle + 1, state);

                    return;
                }
                if (comparisonResult > 0)
                {
                    start = middle + 1;
                }
                else
                {
                    end = middle - 1;
                }
            }
            if (List.Count != 0 && m_Comparator.Compare(state, (T) List[List.Count - 1]) < 0)
                List.Insert(start, state);
            else
                List.Add(state);
        }
    }
}
